#include "stdio.h"
#include "stdlib.h"

typedef int ElemType;

//数据对象
typedef struct LNode {
	ElemType data;
	struct LNode* next;
}LNode, *LinkList;

//动态创建
void CreateList_L(LinkList &L, ElemType arr[],int n) {
	//创建头结点
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;
	for (int i = 0; i < n; i++) {
		//创建新节点
		LinkList P = (LinkList)malloc(sizeof(LNode));
		P->data = arr[i];
		P->next = L->next;
		L->next = P;
	}
}

//归并两个链表
void MergeList_L(LinkList La, LinkList Lb, LinkList& Lc) {
	LinkList pa = La->next; 
	LinkList pb = Lb->next;
	LinkList pc = Lc = La;
	while (pa && pb) {  //pa或者pb不为NULL
		//判断pa结点和pb结点的大小
		if (pa->data > pb->data) {  //如果pb结点比pa结点小
			pc->next = pb;  //将小的结点接入Lc
			pc = pb;  //pc指向小的结点
			pb = pb->next;  //pb向后移
		}
		else {  //如果pa结点比pb结点小
			pc->next = pa;
			pc = pa;
			pa = pa->next;
		}
	}
	pc->next = pa ? pa : pb;  //将剩下的结点接入Lc中
	free(Lb);  //释放Lb的头结点
}


//输出链表
void Print_L(LinkList L) {
	LinkList P = L->next;
	while (P) {
		printf("%3d", P->data);
		P = P->next;
	}
	printf("\n");
}

int main() {
	ElemType arr1[4] = {11,8,5,3};
	ElemType arr2[7] = {20, 15, 11, 9, 8, 6, 2};
	LinkList La;
	CreateList_L(La, arr1, 4);
	LinkList Lb;
	CreateList_L(Lb, arr2, 7);
	Print_L(La);
	Print_L(Lb);
	LinkList Lc;
	MergeList_L(La, Lb, Lc);
	Print_L(Lc);
	return 0;
}